// CodeContracts
// 
// Copyright (c) Microsoft Corporation
// 
// All rights reserved. 
// 
// MIT License
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED *AS IS*, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

#if !MinimalReader && !CodeContracts
using System;
using System.Collections;
using System.Diagnostics;

#if CCINamespace
namespace Microsoft.Cci{
#else
namespace System.Compiler{
#endif
  /// <summary>
  /// Walks a normalized IR, removing push, pop and dup instructions, replacing them with references to local variables.
  /// Requires all Blocks to be basic blocks. I.e. any transfer statement is always the last statement in a block.
  /// (This precondition is established by Reader but not by Normalizer.)
  /// </summary>
  public class Unstacker : StandardVisitor{
    private TrivialHashtable/*!*/ SucessorBlock = new TrivialHashtable();
    private TrivialHashtable/*!*/ StackLocalsAtEntry = new TrivialHashtable();
    private LocalsStack/*!*/ localsStack = new LocalsStack();

    public Unstacker(){
      //^ base();
    }

    public override Statement VisitAssignmentStatement(AssignmentStatement assignment){
      if (assignment == null) return null;
      assignment.Source = this.VisitExpression(assignment.Source);
      assignment.Target = this.VisitTargetExpression(assignment.Target);
      return assignment;
    }
    public override Expression VisitBinaryExpression(BinaryExpression binaryExpression){
      if (binaryExpression == null) return null;
      binaryExpression.Operand2 = this.VisitExpression(binaryExpression.Operand2);
      binaryExpression.Operand1 = this.VisitExpression(binaryExpression.Operand1);
      if (binaryExpression.Type == null) binaryExpression.Type = binaryExpression.Operand1.Type; //Hack: need proper inferencing
      return binaryExpression;
    }
    public override Block VisitBlock(Block block){
      if (block == null) return null;
      LocalsStack stackLocalsAtEntry = (LocalsStack)this.StackLocalsAtEntry[block.UniqueKey];
      if (stackLocalsAtEntry == null){
        //Unreachable code, or the very first block
        stackLocalsAtEntry = new LocalsStack();
      }
      this.localsStack = stackLocalsAtEntry.Clone();
      base.VisitBlock(block);
      Block successor = (Block)this.SucessorBlock[block.UniqueKey];
      if (successor != null) {
        //Dropping off into successor.
        LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[successor.UniqueKey];
        if (targetStack != null && targetStack.top >= 0) {
          //Another predecessor block has already decided what the stack for the successor block is going to look like.
          //Reconcile the stack from this block with the stack expected by the successor block.
          this.localsStack.Transfer(targetStack, block.Statements);
        }
        else {
          this.StackLocalsAtEntry[successor.UniqueKey] = this.localsStack;
        }
      }
      return block;
    }
    public override Statement VisitBranch(Branch branch){
      if (branch == null) return null;
      if (branch.Target == null) return null;
      branch.Condition = this.VisitExpression(branch.Condition);
      int n = this.localsStack.top+1;
      LocalsStack targetStack = (LocalsStack)this.StackLocalsAtEntry[branch.Target.UniqueKey];
      if (targetStack == null){
        this.StackLocalsAtEntry[branch.Target.UniqueKey] = this.localsStack.Clone();
        return branch;
      }
      //Target block has an entry stack that is different from the current stack. Need to copy stack before branching.
      if (n <= 0) return branch; //Empty stack, no need to copy
      StatementList statements = new StatementList(n+1);
      this.localsStack.Transfer(targetStack, statements);
      statements.Add(branch);
      return new Block(statements);
    }
    public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction) {
      if (switchInstruction == null) return null;
      switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
      for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++){
        Block target = switchInstruction.Targets[i];
        if (target == null) continue;
        this.StackLocalsAtEntry[target.UniqueKey] = this.localsStack.Clone();
      }
      return switchInstruction;
    }
    public override ExpressionList VisitExpressionList(ExpressionList expressions) {
      if (expressions == null) return null;
      for (int i = expressions.Count-1; i >= 0; i--)
        expressions[i] = this.VisitExpression(expressions[i]);
      return expressions;
    }
    public override Statement VisitExpressionStatement(ExpressionStatement statement){
      if (statement == null) return null;
      Expression e = statement.Expression = this.VisitExpression(statement.Expression);
      if (e == null || e.Type == CoreSystemTypes.Void) return statement;
      if (e.NodeType == NodeType.Dup) return this.localsStack.Dup();
      return this.localsStack.Push(e);
    }
    public override Expression VisitExpression(Expression expression){
      if (expression == null) return null;
      switch(expression.NodeType){
        case NodeType.Dup: 
        case NodeType.Arglist:
          return expression;
        case NodeType.Pop:
          UnaryExpression uex = expression as UnaryExpression;
          if (uex != null){
            Expression e = uex.Operand = this.VisitExpression(uex.Operand);
            if (e == null) return null;
            uex.Type = CoreSystemTypes.Void;
            return uex;
          }
          return this.localsStack.Pop();
        default:
          return (Expression)this.Visit(expression);
      }
    }
    public override Expression VisitIndexer(Indexer indexer){
      if (indexer == null) return null;
      indexer.Operands = this.VisitExpressionList(indexer.Operands);
      indexer.Object = this.VisitExpression(indexer.Object);
      return indexer;
    }
    public override Method VisitMethod(Method method){
      // body might not have been materialized, so make sure we do that first!
      Block body = method.Body;

      if (method == null) return null;
      BlockSorter blockSorter = new BlockSorter();
      BlockList sortedBlocks = blockSorter.SortedBlocks;
      this.SucessorBlock = blockSorter.SuccessorBlock;
      this.StackLocalsAtEntry = new TrivialHashtable();
      this.localsStack = new LocalsStack();
      ExceptionHandlerList ehandlers = method.ExceptionHandlers;
      for (int i = 0, n = ehandlers == null ? 0 : ehandlers.Count; i < n; i++){
        ExceptionHandler ehandler = ehandlers[i];
        if (ehandler == null) continue;
        Block handlerStart = ehandler.HandlerStartBlock;
        if (handlerStart == null) continue;
        LocalsStack lstack = new LocalsStack();
        this.StackLocalsAtEntry[handlerStart.UniqueKey] = lstack;
        if (ehandler.HandlerType == NodeType.Catch) {
          lstack.exceptionHandlerType = CoreSystemTypes.Object;
          if (ehandler.FilterType != null) lstack.exceptionHandlerType = ehandler.FilterType;
        } else if (ehandler.HandlerType == NodeType.Filter) {
          lstack.exceptionHandlerType = CoreSystemTypes.Object;
          if (ehandler.FilterExpression != null) {
            lstack = new LocalsStack();
            lstack.exceptionHandlerType = CoreSystemTypes.Object;
            this.StackLocalsAtEntry[ehandler.FilterExpression.UniqueKey] = lstack;
          }
        }
      }
      blockSorter.VisitMethodBody(body);
      for (int i = 0, n = sortedBlocks.Count; i < n; i++) {
        Block b = sortedBlocks[i];
        if (b == null) { Debug.Assert(false); continue; }
        this.VisitBlock(b);
      }
      return method;
    }
    public override Expression VisitMethodCall(MethodCall call){
      if (call == null) return null;
      call.Operands = this.VisitExpressionList(call.Operands);
      call.Callee = this.VisitExpression(call.Callee);
      return call;
    }
    public override Expression VisitTernaryExpression(TernaryExpression expression){
      if (expression == null) return null;
      expression.Operand3 = this.VisitExpression(expression.Operand3);
      expression.Operand2 = this.VisitExpression(expression.Operand2);
      expression.Operand1 = this.VisitExpression(expression.Operand1);
      return expression;
    }

    private class LocalsStack{
      private Local[]/*!*/ elements;
      internal int top = -1;
      internal TypeNode exceptionHandlerType;

      private void Grow(){
        int n = this.elements.Length;
        Local[] newElements = new Local[n+8];
        for (int i = 0; i < n; i++) newElements[i] = this.elements[i];
        this.elements = newElements;
      }
      internal LocalsStack(){
        this.elements = new Local[8];
        //^ base();
      }
      private LocalsStack(LocalsStack/*!*/ other) {
        this.top = other.top;
        this.exceptionHandlerType = other.exceptionHandlerType;
        Local[] otherElements = other.elements;
        int n = otherElements.Length;
        Local[] elements = this.elements = new Local[n];
        //^ base();
        n = this.top+1;
        for (int i = 0; i < n; i++)
          elements[i] = otherElements[i];
      }
      internal LocalsStack/*!*/ Clone(){
        return new LocalsStack(this);
      }
      internal AssignmentStatement Dup(){
        int i = this.top;
        Expression topVal;
        if (this.top == -1 && this.exceptionHandlerType != null) {
          topVal = new Expression(NodeType.Dup, this.exceptionHandlerType);
        }else{
          Debug.Assert(i >= 0 && i < this.elements.Length);
          topVal = this.elements[i];
          //^ assume topVal != null;
        }
        Local dup = new Local(topVal.Type);
        if ((i = ++this.top) >= this.elements.Length) this.Grow();
        this.elements[i] = dup;
        return new AssignmentStatement(dup, topVal);
      }
      internal AssignmentStatement Push(Expression/*!*/ expr) {
        //Debug.Assert(expr != null && expr.Type != null);
        int i = ++this.top;
        Debug.Assert(i >= 0);
        if (i >= this.elements.Length) this.Grow();
        Local loc = this.elements[i];
        if (loc == null || loc.Type != expr.Type)
          this.elements[i] = loc = new Local(expr.Type);
        return new AssignmentStatement(loc, expr);
      }
      internal Expression Pop(){
        if (this.top == -1 && this.exceptionHandlerType != null){
          TypeNode t = this.exceptionHandlerType;
          this.exceptionHandlerType = null;
          return new Expression(NodeType.Pop, t);
        }
        int i = this.top--;
        Debug.Assert(i >= 0 && i < this.elements.Length);
        return this.elements[i];
      }
      internal void Transfer(LocalsStack/*!*/ targetStack, StatementList/*!*/ statements) {
        Debug.Assert(targetStack != null);
        if (targetStack == this) return;
        int n = this.top;
        Debug.Assert(n == targetStack.top);
        for (int i = 0; i <= n; i++){
          Local sloc = this.elements[i];
          Local tloc = targetStack.elements[i];
          if (sloc == tloc) continue;
          Debug.Assert(sloc != null && tloc != null);
          statements.Add(new AssignmentStatement(tloc, sloc));
        }
      }
    }
    private class BlockSorter : StandardVisitor{
      private TrivialHashtable/*!*/ VisitedBlocks = new TrivialHashtable();
      private TrivialHashtable/*!*/ BlocksThatDropThrough = new TrivialHashtable();
      private bool lastBranchWasUnconditional = false;
      internal BlockList/*!*/ SortedBlocks = new BlockList();
      internal TrivialHashtable/*!*/ SuccessorBlock = new TrivialHashtable();

      internal BlockSorter(){
        //^ base();
      }

      internal void VisitMethodBody(Block body) {
        if (body == null) return;
        StatementList statements = body.Statements;
        if (statements == null) return;
        Block previousBlock = null;
        for (int i = 0, n = statements.Count; i < n; i++) {
          Block b = statements[i] as Block;
          if (b == null) { Debug.Assert(false); continue; }
          if (previousBlock != null && this.BlocksThatDropThrough[previousBlock.UniqueKey] != null) {
            this.SuccessorBlock[previousBlock.UniqueKey] = b;
          }
          this.VisitBlock(b);
          previousBlock = b;
        }
      }
      public override Block VisitBlock(Block block) {
        if (block == null) return null;
        if (this.VisitedBlocks[block.UniqueKey] != null) {
          return block;
        }
        this.VisitedBlocks[block.UniqueKey] = block;
        this.SortedBlocks.Add(block);
        this.lastBranchWasUnconditional = false;
        base.VisitBlock(block);
        if (!this.lastBranchWasUnconditional)
          this.BlocksThatDropThrough[block.UniqueKey] = block;
        return block;
      }
      public override Statement VisitBranch(Branch branch){
        if (branch == null) return null;
        if (branch.Target == null) return null;
        this.VisitBlock(branch.Target);
        this.lastBranchWasUnconditional = branch.Condition == null;
        return branch;
      }
      public override Statement VisitEndFilter(EndFilter endFilter) {
        endFilter.Value = this.VisitExpression(endFilter.Value);
        this.lastBranchWasUnconditional = true;
        return endFilter;
      }
      public override Statement VisitEndFinally(EndFinally endFinally) {
        this.lastBranchWasUnconditional = true;
        return endFinally;
      }
      public override Statement VisitReturn(Return ret) {
        this.lastBranchWasUnconditional = true;
        return ret;
      }
      public override Statement VisitSwitchInstruction(SwitchInstruction switchInstruction) {
        if (switchInstruction == null) return null;
        switchInstruction.Expression = this.VisitExpression(switchInstruction.Expression);
        for (int i = 0, n = switchInstruction.Targets == null ? 0 : switchInstruction.Targets.Count; i < n; i++){
          Block target = switchInstruction.Targets[i];
          if (target == null) continue;
          this.VisitBlock(target);
        }
        return switchInstruction;
      }
      public override Statement VisitThrow(Throw Throw) {
        this.lastBranchWasUnconditional = true;
        return Throw;
      }
    }
  }
}
#endif
